#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
/*
 * @lc app=leetcode.cn id=315 lang=cpp
 *
 * [315] 计算右侧小于当前元素的个数
 */

// @lc code=start
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        stack<int> single; unordered_map<int, int> first_less;
        for (int i = 0; i < nums.size(); i++) {
            while (!single.empty() && nums[i] < nums[single.top()]) {
                first_less.insert({single.top(), i});
                single.pop();
            }
            single.push(i);
        }
        vector<int> res(nums.size(), 0);
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (first_less.count(i)) res[i] = 1 + res[first_less[i]]; 
        }
        return res;
    }
};
// @lc code=end

